{\rtf1\ansi\ansicpg1252\deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fprq2\fcharset0 Times New Roman;}{\f1\froman\fprq2\fcharset2 Symbol;}}
{\stylesheet{ Normal;}{\s1 heading 1;}{\s2 heading 2;}{\s3 heading 3;}}
{\*\generator Msftedit 5.41.15.1507;}\viewkind4\uc1\pard\fi720\sb100\sa100\qc\ul\f0\fs32 GRASP\par
\par
\pard\fi720\sb100\sa100\qj\ulnone\fs24 GRASP is a powerful tool with many capabilities which enable the user to investigate and handle graphs. The user can use GRASP to create, edit, and research graphs and networks.  We believe that GRASP will be an invaluable tool for learners of graph theory as he/she can tryout various algorithms on their graphs.\par
\pard\sb100\sa100\qj\ul\b Major Features\par
\pard\fi-360\li360\sb100\sa100\qj\tx360\ulnone\b0\f1\'b7\tab\f0 The ease with which graphs are constructed, edges and vertices can be added with just a simple click; movement and resizing of vertices is simply done by dragging\par
\pard\fi-360\li360\sb100\sa100\qj\f1\'b7\tab\f0 Undo/Redo functions are available.\par
\f1\'b7\tab\f0 Execution and step-by-step visualization of different algorithms on graphs (BFS, DFS, shortest path, minimal spanning tree, etc., ) are offered.\par
\f1\'b7\tab\f0 Graph visualization may be printed to a printer.\par
\pard\keepn\s2\sb100\sa100\qj\ul\b System Requirements\par
\pard\fi-360\li360\sb100\sa100\qj\tx360\ulnone\b0\f1\'b7\tab\f0 Java Runtime Environment 1.5+\par
\pard\fi-360\li360\sb100\sa100\qj\f1\'b7\tab\f0 5 MB of disk space\par
\f1\'b7\tab\f0 The number of vertices and edges is limited only by the system resources\par
\f1\'b7\tab\f0 Edge weights range from 1 to 1000\par
\f1\'b7\tab\f0 Only simple graphs can worked upon (i.e. no self loops and multiple edges)\par
\pard\keepn\s1\sb100\sa100\qj\ul\b Creating, Opening and Saving Graphs\par
\pard\keepn\s1\fi720\sb100\sa100\qj\b0 Creating a New Graph\par
\pard\fi720\sb100\sa100\qj\ulnone Click File|New menu or New button on the main toolbar. It prompts for type of graph - directed or undirected - to be created.\par
\ul Opening a saved Graph\par
\ulnone Click File|Open menu or Open button on the main toolbar and then select the graph file (*.gra) you want to open. \par
\pard\keepn\s1\fi720\sb100\sa100\qj\ul Saving a Graph\par
\pard\fi720\sb100\sa100\qj\ulnone Click File|Save menu or Save button on the main toolbar and then select the file where you would like to save the current edited graph.\par
Click File|Save As menu to save the  current edited graph with a new name.\par
\pard\keepn\s1\sb100\sa100\qj\ul\b Adding, Editing and Removing Vertices\par
\pard\keepn\s3\fi720\sb100\sa100\qj\b0 Adding\par
\pard\fi720\sb100\sa100\qj\ulnone Switch to \ldblquote Vertex Mode\rdblquote  by clicking \ldblquote Vertex\rdblquote  button on the toolbar or Tools|Operations|Vertex Mode. Add vertices by left mouse click on the drawing area. Right mouse click on the vertex deletes it.\par
\pard\keepn\s3\fi720\sb100\sa100\qj\ul Selecting\par
\pard\fi720\sb100\sa100\qj\ulnone To select a vertex just click on it. When in \ldblquote Select Mode\rdblquote  you can right click on the vertex for a popup menu that provides options for modify various attributes of the vertex.  Switch to \ldblquote Select Mode\rdblquote  by clicking \ldblquote Sel\rdblquote  button on the toolbar or Tools|Operations|Selection Mode. The following are the attributes of the vertex you can modify:\par
\pard\fi-360\li720\sb100\sa100\qj\tx720\f1\'b7\tab\f0 Shape - rectangle / circle shape of this vertex.\par
\pard\fi-360\li720\sb100\sa100\qj\f1\'b7\tab\f0 Clear all edges - for deleting all the edges from/to this vertex.\par
\f1\'b7\tab\f0 Delete - deletes this vertex.\par
\f1\'b7\tab\f0 Properties - shows a dialog for editing vertex name, height, width, border color and fill color of this vertex..\par
\pard\keepn\s1\fi720\sb100\sa100\qj\ul Moving\par
\pard\fi720\sb100\sa100\qj\ulnone You can move selected vertices anywhere you want by just dragging them.\par
\pard\keepn\s2\sb100\sa100\qj\ul\b Adding, Editing and Removing Edges\par
\pard\keepn\s2\fi720\sb100\sa100\qj\b0 Adding and Removing\b\par
\pard\fi720\sb100\sa100\qj\ulnone\b0 Switch to \ldblquote Edge Mode\rdblquote  by clicking \ldblquote Edge\rdblquote  button on the tool bar or Tools|Operations|Edge Mode. Select a vertex and right-click on another one. An edge will be added between these two vertices if it doesn't exist or it will be removed in case it already exists. The weight of the edge is automatically set to the default value of 1. For directed graphs arc stratring from the first vertex to the second vertex is added.\par
\pard\keepn\s3\fi720\sb100\sa100\qj\ul Editing Edge\par
\pard\fi720\sb100\sa100\qj\ulnone If edges weights are hidden then for making them visible click Tools|Show Weights. or \ldblquote ShowWeights\rdblquote  button on the tool bar.\par
When in \ldblquote Selection Mode\rdblquote  you can right clicking on the edge displays a popup menu for various operations on the edge (selecting an edge is done by clicking on the weight circle, circle will be seen even if weights are hidden )). The following are the options in the popup menu:\par
\pard\fi-360\li1080\sb100\sa100\qj\tx1080\f1\'b7\tab\f0 Invert Edge - for inverting a directed arc \par
\pard\fi-360\li1080\sb100\sa100\qj\f1\'b7\tab\f0 Delete Edge - removes this edge.\par
\f1\'b7\tab\f0 Properties - shows a dialog for changing weight and color of this edge.\par
\pard\fi720\sb100\sa100\qj Edge weights can also be edited in the form adjacency/weight matrix.  Click on \ldblquote AdjMatrix\rdblquote  button on the toolbar or Tools|Adjacency Matrix menu to get the adjacency matrix. Enter 0 for deleting an existing edge. If a non zero value is entered for an edge(which was previously 0) a new edge is created.\par
\pard\sb100\sa100\qj\ul Note:\ulnone  Right Click on the drawing area provides a context menu with the options available from tool bar for ease of use.\par
\pard\keepn\s2\sb100\sa100\qj\ul\b  Status bar\par
\pard\fi720\sb100\sa100\qj\ulnone\b0 The status bar show various messages/status. \par
\pard\fi-360\li1080\sb100\sa100\qj\tx1080\f1\'b7\tab\f0 The location on the drawing area.\par
\pard\fi-360\li1080\sb100\sa100\qj\f1\'b7\tab\f0 Type of graph, number of vertices, number of edges.\par
\f1\'b7\tab\f0 Status of the algorithm (RUNNING/DONE)\par
\f1\'b7\tab\f0 Brief output of the last algorithm executed\par
\pard\keepn\s2\sb100\sa100\qj\ul\b Applied Algorithms\b0\par
\pard\fi720\sb100\sa100\qj\ulnone In GRASP program you can apply the following algorithms on graphs: \par
\pard\fi-360\li1080\sb100\sa100\qj\tx1080\f1\'b7\tab\f0 Breadth First Search\par
\pard\fi-360\li1080\sb100\sa100\qj\f1\'b7\tab\f0 Depth First Search\par
\f1\'b7\tab\f0 Shortest Path (between two vertices)\par
\f1\'b7\tab\f0 Prim\rquote s Minimal Spanning Tree\par
\f1\'b7\tab\f0 Kruskal\rquote s Minimal Spanning Tree\par
\f1\'b7\tab\f0 Topological Sort\par
\f1\'b7\tab\f0 Euler Tour\par
\f1\'b7\tab\f0 Longest Path (between two vertices)\par
\f1\'b7\tab\f0 Maximal Flow (between source and sink)\par
\f1\'b7\tab\f0 Critical Path Analysis (general in project scheduling)\par
\f1\'b7\tab\f0 Graph Coloring\par
\f1\'b7\tab\f0 Travelling Salesman Problem\par
\f1\'b7\tab\f0 Hamilton Tour\par
\pard\fi720\sb100\sa100\qj To apply these algorithms on the graph, select the appropriate option from Run menu. After the program has finished finding the selected item on graph, you will be able to see the operations results. The algorithm operation is shown step by step animated on the graph and also in text form in the message area. The help area displays some information regarding the algorithm.\par
\pard\sb100\sa100\qj\ul Note:\ulnone  Select refresh in edit menu or on the tool bar before performing next operation. While the algorithm is running, editing of the graph is disabled.\par
\ul Technical Note:\ulnone  All algorithms are of exact type, no heuristic is used. As Graph Coloring, Travelling Salesman Problem and Hamilton Tour are NP-Complete problems, finding them on large graphs may take longer (may be even hours for very big graphs) depending on the performance of the computer.\par
\pard\keepn\s2\sb100\sa100\qj\ul\b Printing\par
\pard\fi720\sb100\sa100\qj\ulnone\b0 GRASP offers you the possibility to print Graph's visualization to a printer.\par
To print it on a printer - click File|Print menu. \par
To preview the output - click File|Print Preview ,which will give you the possiblity of printing and seeing how the document will look on a paper.\par
To setup printer's page - click File|Page Setup. \par
}
 